package LeetCode;

import java.util.ArrayList;
import java.util.*;
import java.util.PriorityQueue;

public class LeetCodeMain14 {
    List<List<String>> list=new ArrayList<>();
//    List<String> list1=new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        if (n<=3){
            return list;
        }
        char[][] board=new char[n][n];
        for (char[] c : board) {
            Arrays.fill(c, '.');
        }
        back(n,0,board);
        return list;
    }
    public void back(int n,int row,char[][] board){
        if (row==n){
            List<String> list1=new ArrayList<>();
            for (char[] c:board) {
                list1.add(String.copyValueOf(c));
            }
            list.add(list1);
            return;
        }
        for (int col=0;col<n;col++){
            if (isValid(row,col,n,board)){
                board[row][col]='Q';
                back(n,row+1,board);
                board[row][col]='.';
            }
        }
    }
    public boolean isValid(int row,int col,int n,char[][] board){
        int count=0;
        for (int i = 0; i < row; i++) {
            if (board[i][col]=='Q'){
                return false;
            }
        }
        for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        // 检查 135度⻆是否有皇后
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
    public int minCount(int[] coins) {
        PriorityQueue<Integer> queue=new PriorityQueue<>((o1, o2) -> o2-o1);
        int count=0;
        for (int i = 0; i < coins.length; i++) {
            queue.offer(coins[i]);
        }
        while (!queue.isEmpty()){
            int temp=queue.poll();
            if (temp>2){
                temp-=2;
                queue.offer(temp);
            }
            count++;
        }
        return count;
    }
}
